武汉理工大学 |
您所在的位置：网站首页 › 三元组存储稀疏矩阵 空间计算 › 武汉理工大学 |
|
文章目录
实验目标存储结构稀疏矩阵转置方法1：直接暴力法—— 时间复杂度：O（M.row_num * M.column_num * M.elem_num）方法2：遍历找列法—— 时间复杂度：O（M.column_num * M.elem_num）方法3：快速转置法—— 时间复杂度：O（M.column_num + M.elem_num）
稀疏矩阵相乘方法1：直接暴力法—— 时间复杂度：O（Q.row_num * Q.column_num * N.row_num）方法2：遍历找行法—— 时间复杂度：O（M.elem_num * N.column_num）
稀疏矩阵相加方法：逐个比较法—— 时间复杂度：O（max{A.elem_num，B.elem_num}）
源代码整合写在最后
实验目标
编写程序，采用合适的数据结构存储稀疏矩阵，实现其转置、相乘、相加的算法； 对于每一种操作，尽可能使用时间复杂度较小的算法。 存储结构本文采用 三元组结构 对稀疏矩阵进行压缩存储。 对于矩阵中的每一个非零元素，使用以下结构体存储其 数据、行下标、列下标： //矩阵的非零元素(三元组存储) typedef struct { int row; //元素行下标(由0开始) int column; //元素列下标(由0开始) int value; //元素的值 }Triple;将所有非零元素的结构体 以行序为主序 排列为 结构体数组，即成为稀疏矩阵的存储结构： //稀疏矩阵 typedef struct { Triple data[MAXSIZE + 1]; //元素组成的数据存储数组(data[0]不使用) int row_number; //矩阵行数(由1开始) int column_number; //矩阵列数(由1开始) int elem_number; //矩阵非零元个数 int EachRow_Number[MAXNUM]; //矩阵每一行非零元数量 int EachRow_Index[MAXNUM]; //矩阵每一行非零元在数组的位置 int EachColumn_Number[MAXNUM]; //矩阵每一列非零元数量 int EachColumn_Index[MAXNUM]; //矩阵每一列非零元在数组的位置 }SMatrix;同时使用向量 EachRow_Number / EachColumn_Number 保存每一行/列的非零元素数量， 例如 EachRow_Number [1] = 2 表示第 1 行有 2 个非零元素； 向量 EachRow_Index / EachColumn_Index 保存的是指向某一行/列的某一个元素的 “指针”， 例如 EachRow_Index [1] = 2 表示“指向”了矩阵第 1 行的 data [2] 元素； 这两个向量的引入是为了缩短后续矩阵操作的时间复杂度。 稀疏矩阵转置稀疏矩阵转置总结 3 种方法，记待转置矩阵为 M，转置后矩阵为 T。 方法1：直接暴力法 —— 时间复杂度：O（M.row_num * M.column_num * M.elem_num） /* 矩阵转置(方法1) 直接暴力法 时间复杂度: O(M.row_number * M.column_number * M.elem_number) */ bool TransposeSMatrix_ByViolence(SMatrix M, SMatrix &T) //利用引用来返值 { //属性赋予 T.elem_number = M.elem_number; T.row_number = M.column_number; T.column_number = M.row_number; if (T.elem_number > 0) { int index_T = 1; //T数组下标 for (int i = 0; i for (int index_M = 1; index_M T.elem_number = M.elem_number; T.row_number = M.column_number; T.column_number = M.row_number; if (T.elem_number > 0) { int index_T = 1; //T数组下标 for (int i = 0; i //对M数组遍历 //将M数组的内容以列序为主序, 复制到T的数组中 if (M.data[j].column == i) { T.data[index_T].value = M.data[j].value; T.data[index_T].row = M.data[j].column; T.data[index_T].column = M.data[j].row; //下标自增, 因为T以行序为主序 index_T++; } } } return true; } else return false; }因此 遍历 M 的每一列，将非零元素一个一个放入 T 中 即可，时间复杂度就是 M 的列数乘以 M 的非零元素数。 方法3：快速转置法 —— 时间复杂度：O（M.column_num + M.elem_num）快速转置法的思想是：在遍历 M 整个数据数组的同时，能够 一次性地找到当前非零元素在 T 中的位置 ， 这时候就需要借助先前设置的向量 M.EachColumn_Index “指针”了，这里 M.EachColumn_Index 的使用需要读者细品~ /* 矩阵转置(方法3) 快速转置法 时间复杂度: O(M.elem_number + M.column_number) */ bool TransposeSMatrix_Fast(SMatrix M, SMatrix &T) { T.elem_number = M.elem_number; T.row_number = M.column_number; T.column_number = M.row_number; //设置Index与Number SetSMatrix(M); if (T.elem_number > 0) { for (int i = 1; i if (M.column_number != N.row_number) return false; Q.row_number = M.row_number; Q.column_number = N.column_number; //设置行列的Index和Number SetSMatrix(M); SetSMatrix(N); //把Q非零元个数设置为0 Q.elem_number = 0; //结果累加器行向量，下标为列序号 int Result[MAXNUM] = { 0 }; if (M.elem_number > 0 || N.elem_number > 0) { //双循环实质对M的每一个非零元进行遍历 for (int i = 0; i int n = M.data[j].column; //找到M中乘积元素的列号n //找到N中的第n行，对其遍历 for (int k = N.EachRow_Index[n]; k if (Result[j] != 0) { if (++Q.elem_number > MAXSIZE) return false; //赋值 Q.data[Q.elem_number].row = i; Q.data[Q.elem_number].column = j; Q.data[Q.elem_number].value = Result[j]; //赋值后累加器清零 Result[j] = 0; } } } return true; } else return false; }算法相当于 遍历 M 的所有非零元，每一个非零元对应 N 的某一行，该元素乘以那一行会加入到累加器中，最后总和得出结果； 时间复杂度为 M 的数据数组长度乘以 N 的列数。 稀疏矩阵相加假设有矩阵相加式：A + B = C 方法：逐个比较法 —— 时间复杂度：O（max{A.elem_num，B.elem_num}） /* 矩阵加法 逐个比较法 时间复杂度: O( max{A.elem_number, B_elem_number} ) */ bool AddSMatrix(SMatrix A, SMatrix B, SMatrix &C) { if (A.row_number != B.row_number || A.column_number != B.column_number) return false; C.row_number = A.row_number; C.column_number = A.column_number; //三个数组下标 int index_A = 1; int index_B = 1; int index_C = 1; while (index_A int row_C = row_B; while (row_C == B.data[index_B].row) { C.data[index_C].row = row_C; C.data[index_C].column = B.data[index_B].column; C.data[index_C].value = B.data[index_B].value; index_B++; index_C++; } } else if (row_A C.data[index_C].row = row_C; C.data[index_C].column = A.data[index_A].column; C.data[index_C].value = A.data[index_A].value; index_A++; index_C++; } } else if (row_A == row_B) { int row_C = row_A; //比较列序号 int column_A = A.data[index_A].column; int column_B = B.data[index_B].column; if (column_A > column_B) { C.data[index_C].row = row_C; C.data[index_C].column = column_B; C.data[index_C].value = B.data[index_B].value; index_B++; index_C++; } else if (column_A int sum = A.data[index_A].value + B.data[index_B].value; if (sum != 0) { C.data[index_C].row = row_C; C.data[index_C].column = column_A; C.data[index_C].value = sum; index_C++; } index_A++; index_B++; } } } //将A、B多余元素储存至C while (index_A C.data[index_C].row = B.data[index_B].row; C.data[index_C].column = B.data[index_B].column; C.data[index_C].value = B.data[index_B].value; index_B++; index_C++; } C.elem_number = index_C - 1; return true; }思路简单：就是 A 和 B 一个一个比元素，最后把多余不成对的元素全部加入 C，这样做时间复杂度较小。 源代码整合 #define MAXSIZE 1250 //矩阵中非零元素的最大数量 #define MAXNUM 100 //矩阵行、列的最大数量 #include #include using namespace std; //矩阵的非零元素(三元组存储) typedef struct { int row; //元素行下标(由0开始) int column; //元素列下标(由0开始) int value; //元素的值 }Triple; //稀疏矩阵 typedef struct { Triple data[MAXSIZE + 1]; //元素组成的数据存储数组(data[0]不使用) int row_number; //矩阵行数(由1开始) int column_number; //矩阵列数(由1开始) int elem_number; //矩阵非零元个数 int EachRow_Number[MAXNUM]; //矩阵每一行非零元数量 int EachRow_Index[MAXNUM]; //矩阵每一行非零元在数组的位置 int EachColumn_Number[MAXNUM]; //矩阵每一列非零元数量 int EachColumn_Index[MAXNUM]; //矩阵每一列非零元在数组的位置 }SMatrix; //设置行列Index与Number void SetSMatrix(SMatrix &M) { //初始化为0 for (int i = 0; i //属性赋予 T.elem_number = M.elem_number; T.row_number = M.column_number; T.column_number = M.row_number; if (T.elem_number > 0) { int index_T = 1; //T数组下标 for (int i = 0; i for (int index_M = 1; index_M T.elem_number = M.elem_number; T.row_number = M.column_number; T.column_number = M.row_number; if (T.elem_number > 0) { int index_T = 1; //T数组下标 for (int i = 0; i //对M数组遍历 //将M数组的内容以列序为主序, 复制到T的数组中 if (M.data[j].column == i) { T.data[index_T].value = M.data[j].value; T.data[index_T].row = M.data[j].column; T.data[index_T].column = M.data[j].row; //下标自增, 因为T以行序为主序 index_T++; } } } return true; } else return false; } /* 矩阵转置(方法3) 快速转置法 时间复杂度: O(M.elem_number + M.column_number) */ bool TransposeSMatrix_Fast(SMatrix M, SMatrix &T) { T.elem_number = M.elem_number; T.row_number = M.column_number; T.column_number = M.row_number; //设置Index与Number SetSMatrix(M); if (T.elem_number > 0) { for (int i = 1; i if (M.column_number != N.row_number) return false; Q.row_number = M.row_number; Q.column_number = N.column_number; //设置行列的Index和Number SetSMatrix(M); SetSMatrix(N); //把Q非零元个数设置为0 Q.elem_number = 0; //结果累加器行向量，下标为列序号 int Result[MAXNUM] = { 0 }; if (M.elem_number > 0 || N.elem_number > 0) { //双循环实质对M的每一个非零元进行遍历 for (int i = 0; i int n = M.data[j].column; //找到M中乘积元素的列号n //找到N中的第n行，对其遍历 for (int k = N.EachRow_Index[n]; k if (Result[j] != 0) { if (++Q.elem_number > MAXSIZE) return false; //赋值 Q.data[Q.elem_number].row = i; Q.data[Q.elem_number].column = j; Q.data[Q.elem_number].value = Result[j]; //赋值后累加器清零 Result[j] = 0; } } } return true; } else return false; } /* 矩阵加法 逐个比较法 时间复杂度: O( max{A.elem_number, B_elem_number} ) */ bool AddSMatrix(SMatrix A, SMatrix B, SMatrix &C) { if (A.row_number != B.row_number || A.column_number != B.column_number) return false; C.row_number = A.row_number; C.column_number = A.column_number; //三个数组下标 int index_A = 1; int index_B = 1; int index_C = 1; while (index_A int row_C = row_B; while (row_C == B.data[index_B].row) { C.data[index_C].row = row_C; C.data[index_C].column = B.data[index_B].column; C.data[index_C].value = B.data[index_B].value; index_B++; index_C++; } } else if (row_A C.data[index_C].row = row_C; C.data[index_C].column = A.data[index_A].column; C.data[index_C].value = A.data[index_A].value; index_A++; index_C++; } } else if (row_A == row_B) { int row_C = row_A; //比较列序号 int column_A = A.data[index_A].column; int column_B = B.data[index_B].column; if (column_A > column_B) { C.data[index_C].row = row_C; C.data[index_C].column = column_B; C.data[index_C].value = B.data[index_B].value; index_B++; index_C++; } else if (column_A int sum = A.data[index_A].value + B.data[index_B].value; if (sum != 0) { C.data[index_C].row = row_C; C.data[index_C].column = column_A; C.data[index_C].value = sum; index_C++; } index_A++; index_B++; } } } //将A、B多余元素储存至C while (index_A C.data[index_C].row = B.data[index_B].row; C.data[index_C].column = B.data[index_B].column; C.data[index_C].value = B.data[index_B].value; index_B++; index_C++; } C.elem_number = index_C - 1; return true; } //打印矩阵 void PrintSMatrix(const SMatrix &M) { int index = 1; for (int i = 0; i //判断值是否为0 bool IsZero = true; if (M.data[index].row == i && M.data[index].column == j) { cout 0,2,2},{1,1,3},{1,2,4},{2,0,5},{2,3,6}},3,4,6}; SMatrix T = { {{}, {0,0,1},{0,2,7},{1,1,-4},{2,0,4},{2,1,3},{2,2,5}},4,3,6 }; SMatrix N = { {{},{0,0,-1},{0,1,2},{0,2,4},{1,1,5},{1,2,9},{2,0,5},{2,2,7}},3,4,7 }; cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |